The present invention relates to method and apparatus for detecting "stale data" at addressable storage locations within a data storage system. Data is considered to be stale when it is read a second time without being written between the current read operation and a preceding read operation.
Memory buffers are frequently employed in applications requiring an arrangement that permits data to be alternately written to and read from memory storage locations. In many of these applications, however, operating conditions are frequently encountered where a storage location is addressed for successive read operations without an intervening write operation. For example, memory buffers are widely used for data rate matching purposes, in which the memory write and read operations are conducted at different rates. In circumstances when the read operations are conducted at a rate significantly greater than the rate of the write operations, successive read operations of a storage location can occur without an intervening write operation. Memory buffers are also widely used to change the order of data increments, which is typically accomplished by reading data increments from storage locations in an order different from the order in which they were written. Such operations of memory buffers also can lead to successive read operations of a storage location without an intervening write operation. Occasionally, memory buffers are used in applications requiring the simultaneous performance of rate matching and data ordering operations. This can increase the frequency at which successive read operations occur without an intervening write operation. The occurrence of such successive read operations of a storage location without an intervening write operation results in stale data being delivered repetitively from the storage location of the memory buffer.
An instance in which a data storage system having a stale data detection system has been used to advantage is in an error detection and correction system. The error detection and correction system provides better accuracy and reliability if certain words that are known to be defective can be identified by a technique such as a stale data detection system independently of the error detection and correction algorithm.
For example, a communications system such as a long distance telephone network has noise that may cause random errors in the data. Likewise, a data storage system such as a disk drive system or a tape drive system may have defects in the storage medium which may cause errors in the data. Even occasional intermittent errors in a stream of data can have a devastating effect on the integrity of the information being transmitted by the data stream.
A variety of error correction code (ECC) systems have been developed to detect and correct errors that may occur in an error prone data channel. To enable error detection and correction, a data stream is divided into blocks of data. Each block contains a selected number of words and one or more ECC words are added to the data block before the data block is transmitted through the communication channel or stored. As the data is received, the ECC system checks to determine if any errors have occurred in the data stream during transmission or retrieval of the information. The ECC words that were added to the data block are used to detect and correct a finite number of errors in each data block. Various known error correction codes that may be used to detect or correct errors include Hamming codes, check sums which represent the sum of a numerical value of all words in a block, and a Reed-Solomon code. A description of this code can be found in Peterson, W. Wesley and E. J. Weldon, Jr., Error-Correcting Codes, (MIT PRESS, 2nd Ed. 1972) pp. 1-17, 269-308, and 357-377.
After the data blocks have had ECC words added to them, synchronization information is typically added at fixed intervals in the data before storage or transmission through a data channel. As the data is received by a data buffer, the synchronization information is checked and used to place the data in the corresponding address location of the data buffer specified by the synchronization information. If errors occur in the synchronization information or if for any reason some of the synchronization information is not received, some of the data buffer locations which would normally be written to may not be written to during a data write operation. These unwritten data buffer locations would therefore contain old data which is known to be incorrect. This old data is also referred to as stale data.
Once a block of data has been stored, an error correction algorithm can be used to detect and correct a limited number of errors in the stored block of data. Many commonly used error correction algorithms can correct a greater number of data errors if the existence and location of any data that is known to be incorrect is identified. It is therefore important to detect and flag any stale data locations within the current block of data that represent data from a previous block that was not overwritten when the current block was stored in the data buffer. The ability of the error correction algorithm to detect and correct data is thus improved if these bad words are detected and identified with a flag which corresponds to the bad data word or its address storage location in the data buffer.
One system which detects stale data increases the width of the data buffer by one bit to provide a flag bit for each word location. Thus, if the data is received as 16 bit words, the buffer would be 17 bits wide. This extra bit is set to one when its corresponding data storage address location in the data buffer is written as a block of data is being received. When each data storage location is read during a subsequent error detection and correction process, the extra bit is read and then set to zero. If the extra bit is a one when the data storage location is read, then the data storage location has been written with the current block data since it was last read and the data location contains valid data that is not stale. If the extra bit is a zero, the data storage location has not been over-written by storing data from the current block of data since it was last read, and the data is therefore stale. The extra bit or flag bit can thus be read out from the buffer with each stored data word to indicate to the error detection and correction algorithm whether the word is known to be defective or whether it is potentially correct. These error indications increase the capacity of the error detection algorithm to detect and correct errors in the block of data.
The single extra bit system just described is relatively complicated and expensive to implement. The system must both read the extra bit and set it to zero in the same amount of time in which the system merely reads the other bit positions of any given storage location in the data storage buffer. For a given rate of reading the data buffer, a limited number of options are available to implement the single extra bit system.
One option is to use faster digital memory devices for the extra bit than for the digital memory devices used for the other data storage location at each address. This option requires that the control circuits and control timing signals for the extra bit be faster than the control circuits and control timing signal for the data storage location. Optimizing the timing of control timing signals of two different types of digital memory devices can be difficult to do and expensive in practice. Another option is to increase the speed of the digital memory devices used for the data buffer to match the speed of the digital memory devices used for the extra bit so that the digital memory devices used for the data buffer and the digital memory devices used for the extra bit can share control circuitry. This means that all the digital memory devices in the data buffer must be at least twice as fast as data is actually being retrieved and hence, more expensive.
If the data buffer already uses fast digital memory devices and needs to be operated near its maximum speed, it may be impossible to find a faster digital memory device in order to implement the extra bit used for the stale data detection. Alternatively, the faster memory may be inordinately expensive.